package com.atzxh.heima.algorithm;

/**
 * @author 小红同学
 * @date 2023-06-26-20:29
 * @description 二分查找
 */
public class BinarySearch {

    /**
     * 二分查找基础版
     *
     * @param arr    -->  待查找的升序数组
     * @param target -->  要搜索的目标值
     * @return 如果没找到返回 -1，找到返回目标值。
     */
    public static int binarySearchBasic(int[] arr, int target) {
        // 设置两个指针，及初始值
        int i = 0, j = arr.length - 1;
        // 当 i > j 时，说明目标值不存在
        while (i <= j) {
            // 设置中间指针m，m等于i+j除以2并向下取整
            // int m = (i + j) / 2;
            // 之所以用移位运算替换除2，是因为当i、j的值相加超过int的最大值时，
            //      i+j的值就会变成负数，负数除以二还是负数
            // 但是负数移位的值跟i、j相加除以二的值一样。这样就不会出现m为负数的情况了。
            int m = (i + j) >>> 1;
            if (arr[m] < target) {
                // 此时目标值在m的右侧
                i = m + 1;
            } else if (target < arr[m]) {
                // 此时目标值在m的左侧
                j = m - 1;
            } else {
                return target;
            }
        }
        return -1;
    }

    /**
     * 二分查找改动版
     *
     * @param arr    -->  待查找的升序数组
     * @param target -->  要搜索的目标值
     * @return 如果没找到返回 -1，找到返回目标值。
     */
    public static int binarySearchAlternative(int[] arr, int target) {
        // 改动说明：
        //      1、j 指向了数组右边界的右侧
        //      2、while循环条件变为（i < j）如果还是<=，那么将会变成死循环
        //      3、j = m -1变为j = m  ，因为 j 的含义是j指向的那个数永远不会参与比较
        //          而此时目标值在m的左边，要是还是 j = m -1 ，那么此时的j有可能就是目标值，
        //          最终造成数组有目标值却查不到

        // 设置两个指针，及初始值
        int i = 0, j = arr.length;
        // 当 i > j 时，说明目标值不存在
        while (i < j) {
            // 设置中间指针m，m等于i+j除以2并向下取整
            // int m = (i + j) / 2;
            // 之所以用移位运算替换除2，是因为当i、j的值相加超过int的最大值时，
            //      i+j的值就会变成负数，负数除以二还是负数
            // 但是负数移位的值跟i、j相加除以二的值一样。这样就不会出现m为负数的情况了。
            int m = (i + j) >>> 1;
            if (arr[m] < target) {
                // 此时目标值在m的右侧
                i = m + 1;
            } else if (target < arr[m]) {
                // 此时目标值在m的左侧
                j = m;
            } else {
                return target;
            }
        }
        return -1;
    }

    /**
     * 二分查找--返回最左侧目标值的索引
     *
     * @param arr    -->  待查找的升序数组
     * @param target -->  要搜索的目标值
     * @return 如果没找到返回 -1，找到返回最左侧目标值的索引。
     */
    public static int binarySearchLeftmost(int[] arr, int target) {
        // 设置两个指针，及初始值
        int i = 0, j = arr.length - 1;
        // 候选者的索引
        int candidate = -1;
        // 当 i > j 时，说明目标值不存在
        while (i <= j) {
            int m = (i + j) >>> 1;
            if (arr[m] < target) {
                // 此时目标值在m的右侧
                i = m + 1;
            } else if (target < arr[m]) {
                // 此时目标值在m的左侧
                j = m - 1;
            } else {
                // 记录候选者的位置
                candidate = m;
                j = m - 1;
            }
        }
        return candidate;
    }

    /**
     * 二分查找--返回最右侧目标值的索引
     *
     * @param arr    -->  待查找的升序数组
     * @param target -->  要搜索的目标值
     * @return 如果没找到返回 -1，找到返回最右侧目标值的索引。
     */
    public static int binarySearchRightmost(int[] arr, int target) {
        // 设置两个指针，及初始值
        int i = 0, j = arr.length - 1;
        // 候选者的索引
        int candidate = -1;
        // 当 i > j 时，说明目标值不存在
        while (i <= j) {
            int m = (i + j) >>> 1;
            if (arr[m] < target) {
                // 此时目标值在m的右侧
                i = m + 1;
            } else if (target < arr[m]) {
                // 此时目标值在m的左侧
                j = m - 1;
            } else {
                // 记录候选者的位置
                candidate = m;
                j = m - 1;
            }
        }
        return candidate;
    }
}
